package arrays;

import java.util.*;

/**
 * @author pengfei.hpf
 * @date 2020/3/22
 * @verdion 1.0.0
 *
 * 945. 使数组唯一的最小增量
 * 给定整数数组 A，每次 move 操作将会选择任意 A[i]，并将其递增 1。
 *
 * 返回使 A 中的每个值都是唯一的最少操作次数。
 *
 * 示例 1:
 *
 * 输入：[1,2,2]
 * 输出：1
 * 解释：经过一次 move 操作，数组将变为 [1, 2, 3]。
 * 示例 2:
 *
 * 输入：[3,2,1,2,1,7]
 * 输出：6
 * 解释：经过 6 次 move 操作，数组将变为 [3, 4, 1, 2, 5, 7]。
 * 可以看出 5 次或 5 次以下的 move 操作是不能让数组的每个值唯一的。
 * 提示：
 *
 * 0 <= A.length <= 40000
 * 0 <= A[i] < 40000
 */
public class MinIncrementForUnique {
    public int minIncrementForUnique(int[] A){
        if(A == null || A.length == 0){
            return 0;
        }
        Map<Integer, Integer> map = new HashMap<>();
        for(int i: A){
            int count = map.getOrDefault(i, 0);
            map.put(i, ++count);
        }
        int count = 0;
        Set<Integer> keys = new HashSet<>(map.keySet());
        int reach = 0;
        for(int k: keys){
            int c = map.get(k);
            int moveTo = Math.max(reach, k+ 1);
            while(c > 1){
                while(map.containsKey(moveTo)){
                    moveTo ++;
                }
                reach = moveTo;
                count += moveTo - k;
                map.put(moveTo, 1);
                c --;
            }
        }
        return count;
    }

    public int minIncrementForUniqueII(int[] A){
        if(A == null || A.length == 0){
            return 0;
        }
        Arrays.sort(A);
        int res = 0;
        for(int i=1;i<A.length;i++) {
            if(A[i] == A[i-1]) {
                A[i]++;
                res++;
            } else if(A[i] < A[i-1]) {
                res += A[i-1] - A[i] + 1;
                A[i] = A[i-1] + 1;
            }
        }
        return res;
    }
    public static void main(String[] args){
        System.out.println(new MinIncrementForUnique().minIncrementForUnique(new int[]{3,2,1,2,1,7}));
    }

}
